package 冗余连接II;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

/**
 * @author: AirMan
 * @date: 2025/6/6 11:26
 * @description:
 * 有一种有向树, 该树只有一个根节点，所有其他节点都是该根节点的后继。该
 * 树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。有向树拥有 n 个节点和 n - 1 条边。如图：
 * 现在有一个有向图，有向图是在有向树中的两个没有直接链接的节点中间添加一条有向边。如图：
 * 输入一个有向图，该图由一个有着 n 个节点(节点编号 从 1 到 n)，n 条边，请返回
 * 一条可以删除的边，使得删除该条边之后该有向图可以被当作一颗有向树。
 * 输入描述
 * 第一行输入一个整数 N，表示有向图中节点和边的个数。
 * 后续 N 行，每行输入两个整数 s 和 t，代表这是 s 节点连接并指向 t 节点的单向边
 * 输出描述
 * 输出一条可以删除的边，若有多条边可以删除，请输出标准输入中最后出现的一条边。
 * 输入示例
 */
public class Solution {
    // 整体思路如下：
    // n个节点，n条边，说明只需要删除一条边就能转换为树。
    // 情况一：一个节点的入度为2，可以删除任意一条指向该节点的边
    // 情况二：一个节点的入度为2，只能删除一条特定的边
    // 情况三：不存在入度为2的节点，说明出现了一个环，那么需要找到该环，并删除构成环的边

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[] inDegrees = new int[n + 1];
        int[][] edges = new int[n + 1][2];
        for (int i = 1; i <= n; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            edges[i][0] = u;
            edges[i][1] = v;
            inDegrees[v]++;   // 入度加一
        }
        // 记录入度为二的节点它所依附的两条边
        List<Integer> towInDegree = new ArrayList<>();
        for (int i = edges.length - 1; i > 0; i--) {
            // 遍历的时候需要倒叙遍历，这样删除的时候就会先删除最后一条边
            if (inDegrees[edges[i][1]] == 2) {
                towInDegree.add(i);
            }
        }

        // 情况一，情况二
        if (!towInDegree.isEmpty()) {
            // 尝试删除其中一条边之后，判断是否为树
            int index;
            if (isTreeAfterRemoveEdge(edges, towInDegree.get(0))) {
                index = towInDegree.get(0);
            } else {
                index = towInDegree.get(1);
            }
            int u = edges[index][0];
            int v = edges[index][1];
            System.out.println(u + " " + v);
            return;
        }

        // 情况三
        removeEdge(edges);
    }

    public static int[] father;
    public static int[] rank;

    // 初始化并查集
    public static void init(int n) {
        father = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            father[i] = i;
        }
        rank = new int[n + 1];
    }

    // 找到u的发节点，并进行路径压缩
    public static int find(int u) {
        if (u != father[u]) {
            u = find(father[u]);
        }
        return father[u];
    }

    public static void union(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v) return;
        if (rank[u] < rank[v]) {
            father[u] = v;
        } else if (rank[u] > rank[v]) {
            father[v] = u;
        } else {
            father[v] = u;
            rank[u]++;
        }
    }

    // 情况一或情况二， 删除其中一条边之后，判断是否为树
    public static boolean isTreeAfterRemoveEdge(int[][] edges, int deleteEdge) {
        init(edges.length);
        for (int i = 1; i < edges.length; i++) {
            if (i == deleteEdge) continue;
            if (find(edges[i][0]) == find(edges[i][1])) {
                // 该边的两端节点都已经在并查集中，说明删除的是情况二，删错边了然后出现了环
                return false;
            }
            // 加入到并查集中
            union(edges[i][0], edges[i][1]);
        }
        return true;
    }


    public static void removeEdge(int[][] edges) {
        init(edges.length);
        for (int i = 1; i < edges.length; i++) {
            int u = edges[i][0];
            int v = edges[i][1];
            if (find(u) == find(v)) {
                // 说明成环了，那么删除该边即可
                System.out.println(u + " " + v);
                return;
            } else {
                union(u, v);
            }
        }
    }

}
